package com.javaDemo.node;


/**
 * 公共父节点
 */

class Solution {

    private static int ans;


    private static boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root.val;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
    class Solution1 {
        public boolean search(TreeNode r,TreeNode t){
            if(r==null){
                return false;
            }
            if(r==t){
                return true;
            }
            if(search(r.left,t)){
                return true;
            }
            if(search(r.right,t)){
                return true;
            }
            return false;

        }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(p==root||q==root){
                return root;
            }                                        //这两个节点至少一个是根节点
            boolean ph=search(root.left,p);
            boolean pf=search(root.right,q);
            boolean phi=search(root.right,p);
            boolean pfi=search(root.left,q);

            if(ph&&pf||phi&&pfi){
                return root;
            }                                    //  一个在左子树，一个在右子树
            if(ph&&pfi){
                return lowestCommonAncestor(root.left,p,q);           //两个都在左子树

            }
            return lowestCommonAncestor(root.right,p,q);             //两个都在右子树


        }
    }

    public static int lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    public static void main(String[] args) {
        Integer[] root = {3,5,1,6,2,0,8,7,4};
        TreeNode p=new TreeNode(6);
        TreeNode q=new TreeNode(0);
        System.out.println(lowestCommonAncestor(TreeNode.makeTree(root),p,q));
    }
}